package com.example;

/**
 * @Author loubobooo
 * @Description #21合并两个有序链表
 * @Date 2019/9/27
 */
public class MergeTwoSortedLists {

    /**
     * @return
     * @Author loubobooo
     * @Description 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * @Date 2019/9/27 11:07
     * @Param
     **/
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        // 拼接上更小的那头(谁小拼接谁)
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        // 一样的情况下或者l1.val > l2.val(l1.val >= l2.val)
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode res = dummyHead;

        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val == cur2.val) {
                ListNode temp = new ListNode(cur1.val);
                res.next = temp;
                temp = new ListNode(cur1.val);
                res.next.next = temp;

                res = res.next.next;
                cur1 = cur1.next;
                cur2 = cur2.next;
            } else if (cur1.val > cur2.val) {
                ListNode temp = new ListNode(cur2.val);
                res.next = temp;

                res = res.next;
                cur2 = cur2.next;
            } else {
                // cur1.val < cur2.val
                ListNode temp = new ListNode(cur1.val);
                res.next = temp;
                res = res.next;
                cur1 = cur1.next;
            }

        }
        if (cur1 != null) {
            res.next = cur1;
        }
        if(cur2 != null){
            res.next = cur2;
        }
        return dummyHead.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1){
            return head;
        }
        // 计算下长度
        ListNode p = head;
        int len = 0;
        while(p != null){
            len++;
            p = p.next;
        }
        // 虚拟头
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        // 只需要逆转足够k个一组的
        for(int i = 0; i < len/k && head != null; i++){
            ListNode next = reverse(head,cur,k);
            cur = head;
            head.next = next;
            head = next;
        }
        return dummy.next;
    }

    public static ListNode reverse(ListNode head,ListNode cur,int k){
        int count = 0;
        ListNode prev = null;
        while(head != null && count < k){
            ListNode next = head.next;
            // 头插法
            head.next = prev;
            prev = head;
            head = next;
            count++;
        }
        // 将上一个头接上
        cur.next = prev;
        return head;
    }


    public static void main(String[] args) {
/*        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {1};
        ListNode node1 = new ListNode(1);
        ListNode temp1 = node1;
        for (int i = 0; i < arr1.length; i++) {
            temp1.next = new ListNode(arr1[i]);
            temp1 = temp1.next;
        }
        ListNode node2 = new ListNode(1);
        ListNode temp2 = node2;
        for (int i = 0; i < arr2.length; i++) {
            temp2.next = new ListNode(arr2[i]);
            temp2 = temp2.next;
        }
        MergeTwoSortedLists mergeTwoSortedLists = new MergeTwoSortedLists();
        ListNode listNode = mergeTwoSortedLists.mergeTwoLists2(node1.next, node2.next);
        System.out.println(listNode);*/

        int[] arr1 = {2,3};
        ListNode node1 = new ListNode(1);
        ListNode temp1 = node1;
        for (int i = 0; i < arr1.length; i++) {
            temp1.next = new ListNode(arr1[i]);
            temp1 = temp1.next;
        }
        reverseKGroup(node1,2);
    }

    public static ListNode reverseList2(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }



}